package heap.heapify;

import sortingAdvance.quickSort3Ways.InsertionSort;
import sortingAdvance.quickSort3Ways.SortTestHelper;

/**
 * 三路快速排序
 * mxf
 * 2018年5月28日14:47:28
 */
public class QuickSort3Ways {
    public static void sort(Comparable[] arr) {
        int length = arr.length;
        sort(arr, 0, length - 1);
    }

    private static void sort(Comparable[] arr, int l, int r) {
        if(r - l <= 15) {
            InsertionSort.sort(arr, l, r);
            return;
        }

        // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
        swap( arr, l, (int)(Math.random()*(r-l+1)) + l );

        Comparable v = arr[l];
        // partition
        int lt = l;     // arr[l+1...lt] < v
        int gt = r + 1; // arr[gt...r] > v
        int i = l+1;    // arr[lt+1...i) == v

        while (i < gt) {
            if (arr[i].compareTo(v) < 0) {
                swap(arr, lt + 1, i);
                i++;
                lt++;
            } else if (arr[i].compareTo(v) > 0) {
                swap(arr, gt - 1, i);
                gt--;
            } else {
                i++;
            }
        }
        swap(arr, l, lt);

        sort(arr, l, lt - 1);
        sort(arr, gt, r);
    }

    private static void swap(Comparable[] arr, int l, int r) {
        Comparable v = arr[l];
        arr[l] = arr[r];
        arr[r] = v;
    }

    public static void main(String[] args) {
        Integer[] arr = SortTestHelper.generateRandomArray(1000000, 0, 10);
        QuickSort3Ways.sort(arr);
        SortTestHelper.printArray(arr);
    }
}
